#include <bits/stdc++.h>
using namespace std;
#define INFINITY 50000
#define MAXVERTEX 35
#define NAMESLEN 20
typedef char VRType;
typedef int AdjMatrix;
typedef struct {
	VRType city[50]; 
	int id;
}VertexType;
typedef struct{
	VertexType vex[MAXVERTEX];//城市
	AdjMatrix arcs[MAXVERTEX][MAXVERTEX];//用于存放城市之间路径的矩阵 
	int vexnum,arcnum;//图中的城市数量和路径的数量 
}Mgraph;	
typedef int Pathmatirx[MAXVERTEX][MAXVERTEX];// 二维数组用于弗洛伊德算法中存放经过的城市的id 
typedef int ShortPathTable[MAXVERTEX][MAXVERTEX];//用于存放最短路径上城市的距离 


int is_exitx(Mgraph G,char city[]);
int Transform_id(Mgraph G,char city[]);
void CreateGraph(Mgraph &G);
void ShortestPath_DIJ(Mgraph G,int v0);
void ShortestPath_FLOYD(Mgraph G,Pathmatirx &P, ShortPathTable &D);
void System(Mgraph &G);


int is_exitx(Mgraph G,char city[])//判断城市是否存在的方法，存在返回1否则返回0 
{
	int flag=0;
	
	for(int i = 0;i<G.vexnum;i++){
		if (strcmp(city, G.vex[i].city) == 0)
		{
			flag=1;
			break;
		}
	}
	
	return flag;
} 



void ShortestPath_DIJ(Mgraph G)//迪杰斯特拉算法，计算一个城市到其他所有城市的最短路径 
{
	int D[MAXVERTEX],P[MAXVERTEX];
	int v,u,i,j,k,w,min,a,v0;
	char name[10];
	int final[MAXVERTEX];//用于判断城市是否已经访问 
	char *id[MAXVERTEX];//定义一个字符串数组用于正向输出路径 
	id[0]='\0';//初始化数组为空 
	printf("请输入起点城市\n");
	scanf("%s",&name);
	while(!is_exitx(G,name))
	{
		printf("你输入的城市不存在，请重新输入：\n");
		scanf("%s",&name);
	}
	
	v0=Transform_id(G,name);
	
	for(v=0;v<G.vexnum;v++)
	{
		final[v]=0;//初始化为0 
	    D[v]=G.arcs[v0][v];//两个城市之间开始时最短路径就为两个城市之间的路径长度 
	    P[v]=0;//初始化每个城市的前一个城市的id 
		if(D[v]<INFINITY)//判断城市之间是否有边，有边则前一个城市就为v0，否为为0 
		{
			P[v]=v0;
		}
		else{
			P[v]=0;
		}
	}
	
	P[v0]=-1;//用来后面判断正序输出是否到起点 
	D[v0]=0;//起点到起点的路径设为0； 
	final[v0]=1;//访问过就变为1 
	
	for(i=0; i<G.vexnum; i++)//开始循环，依次找出路径最短的城市 
	{
		min = INFINITY;//第一最小值为无穷 
		for(w=0; w<G.vexnum; w++)//找出与v0相距最近的第一个城市 
		{
			if(!final[w]&&D[w]<min)//判断该城市是否已经访问过，并且与v0之间的路径是否小于min值 
			{
					u=w;             //如果条件成立，则将该城市赋值给u，更新最小值min 
					min=D[w];			
			}
		}
		
		final[u]=1;//找出一个未被访问的最小路径的城市后标记该城市已经访问 
		
		for(w=0; w<G.vexnum; w++)//用来判断v0到该城市的直接路径是否小于经过其他城市的路径 
		{
			if(!final[w]&&(min+G.arcs[u][w]<D[w]))//如果该顶点未被访问过并且最小值与上个城市之间路径的和小于该城市与v0之间的路径长度 
			{
				D[w]=min+G.arcs[u][w];//修改该城市的最短路径 
				P[w]=u;//修改该城市的前一个城市的顶点为u 
			}
		}
	}
	
	for(i=0;i<G.vexnum;i++){//此循环用于输出v0到各个城市所经过的城市 
		if(i!=v0)//v0到v0没有路径 
		{
			if(D[i]==INFINITY)
			{
				printf("%s到%s之间没有路径\n",G.vex[v0].city,G.vex[i].city);
			}
			else{
				j=0;
				printf("%s到%s最短路径长度为：%d\n",G.vex[v0].city,G.vex[i].city,D[i]);
				v=P[i];//中间变量v就等于该城市的前一个城市 
				printf("路径为：%s->",G.vex[v0].city);
				if(v!=-1)//因为如果v0的节点为零，再途径v0的城市不能输出v0，所以改为-1  
				{
					while(v!=-1)//逐个输出途径城市 ，但是路径是倒叙 
					{
						id[j] = G.vex[v].city;// 将城市的名称存放在字符串数组id【】中，用于正序输出 
						j++;//输入向后移动一个空间 
						v=P[v];//继续向前找途径城市 
					}
					j=j-1;//最后一为数组值为'\0'，所以要减一 
					k=j;//判断循环 
					for(int f=0;f<k;f++)//输出城市 
					{
						printf("%s->",id[--j]);
					}
				}
				printf("%s\n",G.vex[i].city);
			}
		}
		printf("\n");
	}
	
	printf("======================================================================\n");
	printf("======================================================================\n");
} 


void ShortestPath_FLOYD(Mgraph G,Pathmatirx &P, ShortPathTable &D)//弗洛伊德算法计算某个城市到另一个城市的最短路径 
{
	int c,d,v,w,u,temp;
	char a[NAMESLEN],b[NAMESLEN];//用于输入起点和终点城市 
	
	for(v=0;v<G.vexnum;++v)//初始化邻接矩阵 
	{
		for(w=0;w<G.vexnum;++w)
		{
			D[v][w]=G.arcs[v][w];//两个城市之间的路径赋值 
			P[v][w]=w;//设前一个城市为w 
		}
	}
	
	for(u=0;u<G.vexnum;++u)//用于计算最短路径 
	{
		for(v=0;v<G.vexnum;++v)
		{
			for(w=0;w<G.vexnum;++w)
			{
				if(D[v][u]+D[u][w]<D[v][w])//如果城市v和城市w之间的路径长度大于城市v经过城市u再到城市w的长度，则更改路径和路径长度 
				{
					D[v][w]=D[v][u]+D[u][w];
					P[v][w]=P[v][u]; 
				}
			}
		}
	}
	
	printf("请输入起点城市：\n");//需要知道起点和终点城市是否存在！！！！ 
	scanf("%s",&a); 
	
	while(!is_exitx(G,a))
	{
		printf("你输入的城市不存在，请重新输入：\n");
		scanf("%s",&a);
	}
	
	printf("请输入终点城市：\n");
	scanf("%s",&b);
	
	while(!is_exitx(G,b))
	{
		printf("你输入的城市不存在，请重新输入：\n");
		scanf("%s",&b);
	}
	
	c=Transform_id(G,a);
	d=Transform_id(G,b); 
	
	if(D[c][d]==INFINITY)//如果两个城市没有路径 
	{
		if(c!=d)
		{
			printf("%s到%s之间没有路径！",a,b);
		}
	}
	else
	{
		printf("%s到%s之间最短路径为：%d\n",G.vex[c].city,G.vex[d].city,D[c][d]);
		temp=P[c][d];
		printf("路径：%s",G.vex[c].city);
		while(temp!=d)//同迪杰斯特拉一样，只不过此次输出的就是正序 
		{
			printf("->%s",G.vex[temp].city);
			temp=P[temp][d];
		}
		printf("->%s\n",G.vex[d].city);
	}
	
	printf("======================================================================\n");
	printf("======================================================================\n");
}


void Traversal(Mgraph &G)//遍历所有城市信息  输出矩阵 
{
	int a = 0;
	//printf("====================================================================");
	//printf("====================================================================");
	//printf("====================================================================\n");
	printf("===============各城市名称和对应编号===============\n");
	
	for(int i=0;i<G.vexnum;i++)
	{
		if(i%3==0)
		{
			printf("\n");
			printf("--------------------------------------------------\n");
		}
		printf("|%8s--%2d|    ",G.vex[i].city,i);
	}
	
	printf("\n==================================================\n");
	printf("城市编号及对应矩阵图\n");
	printf(" 编号 "); 
	
	for(int i=0;i<G.vexnum;i++)
	{
		printf("|%4d|",G.vex[i].id);
	}
	
	printf("\n");
	printf("======================================================================\n");
    printf("======================================================================\n");
	for(int i=0;i<G.vexnum;i++)
    {
    	printf("|%4d|",G.vex[i].id);
        for(int j=0;j<G.vexnum;j++)
        {	
        	if(G.arcs[i][j]!=INFINITY){
           		printf("|%4d|", G.arcs[i][j]);
           	}
           	else{
           		printf("| ∞ |");	
			}
        }
        printf("\n");
       	printf("======================================================================\n");
    	printf("======================================================================\n");
    }
}

void System(Mgraph &G){
	Pathmatirx P;
	ShortPathTable D;
	char a[NAMESLEN];
	char b;
	while(1)
	{
		int i=3;
		printf("*************************导航最短路径查询系统*************************\n");
        printf("======================================================================\n");
        printf("=============== 1.求一个城市到其他所有城市的最短路径 =================\n");
        printf("===============  2.求某个城市到另一个城市的最短路径  =================\n");
        printf("请输入您的选择： ");
       	
       	scanf("%s", &b);//如果输入的是字符怎么办
       	getchar();
		switch(b)
		{
			 
			case '1':	
				printf("计算起点到各个顶点的最短路径。\n");
				ShortestPath_DIJ(G);
				break;
			case '2':
				printf("计算一个点到另一个点的最短路径\n");
				ShortestPath_FLOYD(G,P,D);
				break;
			case '0':
				printf("退出系统！\n");
				exit(-1); 
				break;
			default:
				printf("输入有误，请重新输入\n");
				break;
		}
	}
} 


int main()
{
	Mgraph G;
	printf("======================================================================\n");
	printf("===============              创建交通图              =================\n");
	CreateGraph(G);
	printf("===============             交通图建立完毕           =================\n");
	printf("======================================================================\n");
	System(G);
	
	return 0;
}
int Transform_id(Mgraph G,char city[])//获取城市id的函数
{
	int i,id;
	
	for(i=0;i<G.vexnum;i++)
	{
		if(strcmp(G.vex[i].city,city)==0)
		{
				id=G.vex[i].id;
		}
	}
	
	return id;
} 
	
	
void CreateGraph(Mgraph &G)//创建城市交通图 
{	ifstream infile1;
	infile1.open("v&e.txt", ios::in);
	if (!infile1.is_open())
	{
		cout << "读取文件失败" << endl;
	}
int k[100];
for(int i=0;i<2;i++)
infile1>>k[i];
	G.vexnum = k[0];	//交通图中初始化城市的数量 
	G.arcnum = k[1];  //交通图中初始化路径的数量 
	int a,d,e,f,g,i,j,w,num;
	char b[NAMESLEN],c[NAMESLEN];

	for(i=0;i<G.vexnum;i++)//初始化图的顶点id 
	{
		G.vex[i].id=i;
	}
	printf("===============            初始化交通图路线          =================\n");
	strcpy(G.vex[0].city,"郑州");
	strcpy(G.vex[1].city,"北京");
	strcpy(G.vex[2].city,"西安");
	strcpy(G.vex[3].city,"武汉");
	strcpy(G.vex[4].city,"徐州");
	strcpy(G.vex[5].city,"天津");
	strcpy(G.vex[6].city,"呼和浩特");
	strcpy(G.vex[7].city,"兰州");
	strcpy(G.vex[8].city,"成都");
	strcpy(G.vex[9].city,"株洲");
	strcpy(G.vex[10].city,"南昌");
	strcpy(G.vex[11].city,"上海");
	strcpy(G.vex[12].city,"乌鲁木齐");
	strcpy(G.vex[13].city,"西宁");
	strcpy(G.vex[14].city,"昆明");
	strcpy(G.vex[15].city,"贵阳");
	strcpy(G.vex[16].city,"南宁");
	strcpy(G.vex[17].city,"柳州");
	strcpy(G.vex[18].city,"广州");
	strcpy(G.vex[19].city,"深圳");
	strcpy(G.vex[20].city,"福州");
	strcpy(G.vex[21].city,"大连");
	strcpy(G.vex[22].city,"沈阳");
	strcpy(G.vex[23].city,"长春");
	strcpy(G.vex[24].city,"哈尔滨");

	 

	for(i=0;i<G.vexnum;i++)//初始化图矩阵 
	{
		for(int j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j]=INFINITY;
		}
	}
	G.arcs[0][1] = 695;//郑州-----北京 
	G.arcs[1][0] = 695;
	
	G.arcs[0][2] = 511;//郑州-----西安 
	G.arcs[2][0] = 511;
	
	G.arcs[0][3] = 534;//郑州-----武汉 
	G.arcs[3][0] = 534;
	
	G.arcs[0][4] = 349;//郑州-----徐州 
	G.arcs[4][0] = 349;
	
	G.arcs[1][5] = 137;//北京-----天津 
	G.arcs[5][1] = 137;
	
	G.arcs[4][5] = 674;//天津-----徐州 
	G.arcs[5][4] = 674;
	
	G.arcs[5][22] = 704;//天津-----沈阳 
	G.arcs[22][5] = 704;
	
	G.arcs[22][21] = 397;//沈阳-----大连 
	G.arcs[21][22] = 397;
	
	G.arcs[22][23] = 305;//沈阳-----长春 
	G.arcs[23][22] = 305;
	
	G.arcs[23][24] = 242;//长春-----哈尔滨 
	G.arcs[24][23] = 242;
	
	G.arcs[1][6] = 668;//北京-----呼和浩特 
	G.arcs[6][1] = 668;
	
	
	G.arcs[6][7] = 1145;//呼和浩特-----兰州 
	G.arcs[7][6] = 1145;
	
	G.arcs[7][12] = 1892;//兰州-----乌鲁木齐 
	G.arcs[12][7] = 1892;
	
	G.arcs[7][13] = 216;//兰州-----西宁 
	G.arcs[13][7] = 216;
	
	G.arcs[7][2] = 676;//兰州-----西安 
	G.arcs[2][7] = 676;
	
	G.arcs[2][8] = 842;//西安-----成都 
	G.arcs[8][2] = 842;
	
	G.arcs[8][14] = 1100;//成都-----昆明 
	G.arcs[14][8] = 1100;
	
	G.arcs[8][15] = 967;//成都-----贵阳 
	G.arcs[15][8] = 967;
	
	G.arcs[14][15] = 639;//贵阳-----昆明 
	G.arcs[15][14] = 639;
	
	G.arcs[15][17] = 607;//贵阳-----柳州 
	G.arcs[17][15] = 607;
	
	G.arcs[17][16] = 255;//柳州-----南宁 
	G.arcs[16][17] = 255;
	
	G.arcs[15][9] = 902;//贵阳-----株洲 
	G.arcs[9][15] = 902;
	
	G.arcs[9][17] = 672;//柳州-----株洲 
	G.arcs[17][9] = 672;
	
	G.arcs[3][9] = 409;//武汉-----株洲 
	G.arcs[9][3] = 409;
	
	G.arcs[9][18] = 675;//株洲-----广州 
	G.arcs[18][9] = 675;
	
	G.arcs[18][19] = 140;//广州-----深圳 
	G.arcs[19][18] = 140;
	
	G.arcs[9][10] = 367;//株洲-----南昌 
	G.arcs[10][9] = 367;
	
	G.arcs[10][11] = 825;//南昌-----上海 
	G.arcs[11][10] = 825;
	
	
	G.arcs[10][20] = 622;//南昌-----福州 
	G.arcs[20][10] = 622;
	
	G.arcs[11][4] = 651;//徐州-----上海 
	G.arcs[4][11] = 651;
	
}
